package com.sakura.动态规划;

public class Code32_最长有效括号 {

    public int longestValidParentheses(String str) {
        char[] s = str.toCharArray();
        int n = s.length;
        int[] dp = new int[n];
        int ans = 0;
        for (int i = 1, pre; i < n; i++) {
            if (s[i] == ')') {
                pre = i - dp[i - 1] - 1;
                if (pre >= 0 && s[pre] == '(') {
                    dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }
}
